Table lookup is a common operation performed by many Internet switches and routers. As depicted in FIG. 1, a typical switch includes a Forwarding Engine, Line Cards, and a Switching Fabric which can be implemented as Application Specific Integrated Circuits (ASICs). The forwarding engine is a processor that has a group of tables which may include an L2 table with MAC addresses, an L3 table with IP addresses, a NetFlow table with flow identifiers, and other tables with L4-L7 information. The address lookup function examines a packet's destination address, stored in a table, and selects an output port associated with that address.
Looking up an address in a table is usually combined with a hashing operation and the performance of the lookup process depends on both the hash function and the table organization. In the switch depicted in FIG. 1, the hashing operation is performed by Linear Feedback Shift Registers (LFSRs) for high speed. Doing a lookup operation means searching for an item in the table. When the item is found (Hit), the table location will also contain other information related to the further processing for that item. For example, on L2 forwarding tables, lookup is done on MAC addresses and the related information contained in the table is the port that first received the MAC address. On L3 forwarding tables, lookup is done on IP addresses and the related information is the port where packets destined to that IP address should be sent.
When the item is not found on the table it will be inserted (Learning phase), and if it is not possible to learn a new entry, then the item will be dropped (Miss). Usually hardware lookups resulting in a miss will be redirected to software, thus slowing down the performance. Tables can be implemented in various ways, including using RAM (e.g. DRAM, Synchronous DRAM (SDRAM), Reduced Latency DRAM (RLDRAM) or Ternary Content Addressable Memory (TCAM)).
A common search mechanism employed is called D-Left Hashing which is depicted in the flow chart of FIG. 2. D-Left hashing uses two hash tables with two different primitive polynomial hash functions. The search key is hashed with two different and uncorrelated hash functions. The hash functions reduce the key from a large number of bits to a smaller number of bits in a pseudo-random manner. The result of the first hash function is used as an index into the left table. An identical process is followed by using the second hash function and the right table, in parallel with the process performed by the left table.
Since keys in the tables are unique, a key which matches the key data of an entry results in a unique match, and the associated data of that entry is output from the search function. Each table contains as many rows, or buckets, as there are possible results from the hash function. For example, if the hash function produces an 11-bit value then there will be 211, or 2048, buckets in each table. If each table bucket contains four cells, then up to four keys which hash to the same bucket index can be stored in that bucket. The key data field in each of the buckets is compared against the original search key to determine if there is a match.
The D-Left hashing mechanism could easily generate hashing overflow, when all cells are occupied by the index of these two hash tables. As such, additional hardware resources are needed to resolve the overflow. The more overflow generated, the more additional hardware resources are needed.
The challenges in the field of table lookup continue to increase with demands for more and better techniques having greater flexibility and adaptability. Therefore, a need has arisen for a new apparatus and method for efficient and low-cost table lookup techniques.